# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.

from Graph import Graph

class AdjListGraph(Graph):

    def __init__(self, multi=False, directed=False):
        Graph.__init__(self, multi, directed)
        self.adj_list = {}
        self._E = 0

    def add_edge(self, e):
        for v in e:
            self.add_vertex(v)
        u = e[0]
        v = e[1]
        if self.multi or v not in self.adj_list[u]:
            self.adj_list[u].append(v)
            self._E += 1
        if not self.directed:
            if self.multi or u not in self.adj_list[v]:
                self.adj_list[v].append(u)

    def add_vertex(self, u):
        self.adj_list.setdefault(u, [])

    def V(self):
        return len(self.adj_list)

    def E(self):
        return self._E

    def degree_in(self, u):
        "O(|E|)/O(1)"
        ret = 0
        if self.directed:
            for ulist in self.adj_list:
                if self.multi:
                    for _u in ulist:
                        if _u == u:
                            ret += 1
                else:
                    if u in ulist:
                        ret += 1
        return ret

    def degree_out(self, u):
        "O(1)/O(1)"
        return len(self.adj_list[u])

    def transpose(self):
        "O(|E|)/O(|E|)"
        adj_list = dict([(u,[]) for u in self.adj_list])
        for u, u_neighbour_list in self.adj_list.iteritems():
            for v in u_neighbour_list:
                adj_list[v].append(u)
        self.adj_list = adj_list

    def unmulti(self):
        "O(|E|)/O(|V|)"
        for u, u_neighbour_list in self.adj_list.iteritems():
            present = [False for w in self.adj_list]
            new_neighbour_list = []
            for v_index, v in u_neighbour_list.iteritems():
                if not present[v] and u != v:
                    present[v] = True
                    new_neighbour_list.append(v)
            self.adj_list[u] = new_neighbour_list

    def square(self):
        # TODO nefunguje pro multigrafy, konkretne pro smycky
        #      does not work for multigraphs, specifically for self-loops
        "O(|V|^3)/O(|V|+|E|)"
        adj_list = [[] for u in self.adj_list]
        for u in self.vertices():
            for v in self.adj_list[u]:
                for w in self.adj_list[v]:
                    adj_list[u].append(w)
        self.adj_list = adj_list
        self.unmulti()

    def vertices(self):
        "O(1)/O(1)"
        return self.adj_list.keys()

    def edges(self):
        for u, ulist in self.adj_list.iteritems():
            for v in ulist:
                yield (u,v)

    def universal_sink(self):
        "O(|E|)/O(1)"
        ret = None
        for v in self.vertices():
            if self.degree_out(v) == 0 and self.degree_in(v) == self.V() - 1:
                ret = v
                break

        return ret

    def neighbours(self, u):
        "O(1)/O(|V|)"
        return self.adj_list[u]
